package org.aplombh.java.interview.newcoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class NC37_合并区间 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param intervals Interval类ArrayList
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        Collections.sort(intervals);

        int r = -1;
        int l = -1;

        ArrayList<Interval> res = new ArrayList<>();
        for (Interval t : intervals) {
            if (t.start > r) {
                if (l != -1) {
                    res.add(new Interval(l, r));
                }
                l = t.start;
                r = t.end;
            }
            r = Math.max(r, t.end);
        }
        if (l != -1)
            res.add(new Interval(l, r));
        return res;
    }
}

class Interval implements Comparable<Interval> {
    int start;
    int end;

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Interval o) {
        return this.start - o.start;
    }
}
